package leetcode.code0312;

/**
 * 递归超时 No.1
 *
 * @author CaoYu
 * @date 2021年10月2日
 * @description
 */
public class Solution1 extends Solution312 {

	@Override
	public int maxCoins(int[] nums) {
		int len = nums.length;
		int[][] next = new int[len][3];
		this.initNext(next);
		return maxCoins(nums, next, len);
	}

	private void initNext(int next[][]) {
		for (int i = 0; i < next.length; i++) {
			next[i][0] = 0;
			next[i][1] = i - 1;
			next[i][2] = i + 1;
		}
	}

	private void takeNext(int next[][], int index) {
		next[index][0] = 1; // 占用
		int left = next[index][1];
		int right = next[index][2];
		if (left >= 0)
			next[left][2] = right;
		if (right < next.length)
			next[right][1] = left;
	}

	private void freeNext(int next[][], int index) {
		next[index][0] = 0; // 释放
		int left = next[index][1];
		int right = next[index][2];
		if (left >= 0)
			next[left][2] = index;
		if (right < next.length)
			next[right][1] = index;
	}

	private int maxCoins(int[] nums, int next[][], int rest) {
		if (rest == 0)
			return 0;
		int ans = Integer.MIN_VALUE;
		for (int i = 0; i < nums.length; i++) {
			if (next[i][0] == 0) {
				int l = next[i][1] == -1 ? 1 : nums[next[i][1]];
				int r = next[i][2] == nums.length ? 1 : nums[next[i][2]];
				int coin1 = l * nums[i] * r;
				this.takeNext(next, i);
				int coin2 = this.maxCoins(nums, next, rest - 1);
				this.freeNext(next, i);
				ans = Math.max(ans, coin1 + coin2);
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
	}

}
